package leetcode.dp;

/**
 * @author mazouri
 * @create 2021-12-30 17:41
 */
public class _5_longestPalindrome_recursion {
    public int longestPalindrome(String s) {
        return helper(s, 0, s.length() - 1);
    }

    private int helper(String s, int i, int j) {
        if (i == j) return 1;
        if (i > j) return 0;

        if (s.charAt(i) == s.charAt(j) && helper(s, i + 1, j - 1) == j - i - 1) {
            return (j - i - 1) + 2;
        } else {
            int lo = helper(s, i, j - 1);
            int hi = helper(s, i + 1, j);
            return Math.max(lo, hi);
        }
    }

    public static void main(String[] args) {
        System.out.println(new _5_longestPalindrome_recursion().longestPalindrome("bbbabbb"));
    }
}
